/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"

using namespace std;


/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
    rootPid = -1;
    treeHeight = 0;
}


/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
    RC rc;

    if( ( rc = pf.open( indexname, mode ) ) < 0 )
        return rc;

    /*
     * If the endPid is not 0, then the page file contains something
     * (at least some page information in the page with id 0).
     */
    if(pf.endPid()!=0) //if pageFile is not empty
    {
        if( ( rc = getRootHeight() ) < 0 )
            return rc;
    }

    /*
     * If the endPid is 0, then the page file is empty (a new page file),
     * then set the rootPid to -1, indicating there is no root page
     * in the page file, and the B+ tree is empty. Also, set treeHeight to 0
     */
    else
    {
        rootPid = -1;
        treeHeight = 0;
    }
    return 0;
}


/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
    RC rc;

    if( ( rc = setRootHeight() ) < 0 )
        return rc;
    return pf.close();
}


/*
 * Get the rootPid and treeHeight information from page 0
 */
RC BTreeIndex::getRootHeight()
{
    char buffer[PageFile::PAGE_SIZE];
    RC rc;

    // read the page with id 0 into the buffer
    if( ( rc = pf.read(0,buffer) ) < 0 )
        return rc;

    // get the rootPid information from the first sizeof(PageId)
    memcpy(&rootPid, buffer+ROOT_PID_START_POS,sizeof(PageId));
    // get the treeHeight information from the following sizeof(int)
    memcpy(&treeHeight, buffer+TREE_HEIGHT_START_POS,sizeof(int));
	// get least Key Cursor from the following size of IndexCursor
	memcpy(&leastKeyCursor, buffer+LEAST_KEY_CURSOR_POS, sizeof(IndexCursor));

    return 0;
}


/*
 * Save the rootPid and treeHeight information into page 0
 */
RC BTreeIndex::setRootHeight()
{
    char buffer[PageFile::PAGE_SIZE];

    // store the information into the temporary buffer
    memcpy(buffer+ROOT_PID_START_POS,&rootPid,sizeof(PageId));
    memcpy(buffer+TREE_HEIGHT_START_POS,&treeHeight,sizeof(int));
	memcpy(buffer+LEAST_KEY_CURSOR_POS, &leastKeyCursor, sizeof(IndexCursor));

    // write the buffer to the page with id 0
    return pf.write(0,buffer);
}


/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
    //char buffer[PageFile::PAGE_SIZE];
    RC rc;
    int keyBack;
    bool overflow = false;

    // if the treeHeight is 0, then this is a new B+ tree without any nodes
    if( treeHeight == 0 )
    {
        BTLeafNode root;

        root.insert( key, rid );
        if( ( rc = root.write(1,pf) ) < 0 )
            return rc;

        rootPid = 1;
        treeHeight = 1;
        return 0;
    }

    // if the treeHeight is not 0:
    else
    {
        if( ( rc = insertRecursive( key, rid, rootPid, treeHeight, overflow, keyBack ) ) < 0 )
        {
            fprintf( stderr, "Error: while insert into the node with page id %d\n", rootPid );
            return rc;
        }

        if( overflow ) //if overflow at root
        {
            /*
             * When overflow, we need to create a new root,
             * and the new root is a non-leaf node
             */
            BTNonLeafNode root;

            /*
             * the left pid should be the original root,
             * and the right pid should be the newly created node,
             * which is in the last page of the page file.
             */
            root.initializeRoot( rootPid, keyBack, pf.endPid() - 1 );
            // the new root is written into the end of the page file
            root.write( pf.endPid(), pf );
            // set the rootPid to be the last page
            rootPid = pf.endPid() - 1;
            treeHeight++; // increment the height by 1
        }
    }

    // when the old root does not overflow, do nothing
    return 0;
}


/*
 * A recursive call by insert function, insert the the (key, rid) pair
 * into the current root (treat as the root of a subtree),
 * whenever there is a overflow in the next level, set overflow to true.
 * @param key[IN] the key to be inserted.
 * @param rid[IN] the record id to be inserted.
 * @param currPid[IN] the pid of the root of the current subtree.
 * @param height[IN] the height of the subtree
 * @param overflow[OUT] if the next level of node is split, overflow is set to true
 * @param keyBack[OUT] if the next level of node is split, the key passed back is set
 */
RC BTreeIndex::insertRecursive( int key, const RecordId& rid, PageId currPid, int height, bool& overflow, int& keyBack )
{
    RC rc;

    //at leaf insert
    if( height == 1 )
    {
        BTLeafNode currLeaf;
        currLeaf.read(currPid,pf);

        // leaf full, insert key rid and split and return overflow to parent node.
        if( currLeaf.isFull() )
        {
            BTLeafNode sibling;
            currLeaf.insertAndSplit( key, rid, sibling, pf.endPid(), keyBack );
            overflow = true;

            // write the new sibling node into the page file at pf.endPid()
            if( ( rc = sibling.write( pf.endPid(), pf ) ) < 0 )
            {
              fprintf( stderr, "Error: while writing the new sibling node into the end of page file\n" );
              return rc;
            }

            // and write the modified current leaf node into the page file
            if( ( rc = currLeaf.write( currPid, pf ) ) < 0 )
            {
              fprintf( stderr, "Error: while writing the updated current node into the page file\n" );
              return rc;
            }

            return 0;
        }

        else //leaf not full, just insert key and rid and set overflow to false
        {
            currLeaf.insert( key, rid );
            overflow = false;

            // write the modified current leaf node into the page file
            if( ( rc = currLeaf.write( currPid, pf ) ) < 0 )
            {
              fprintf( stderr, "Error: while writing the updated current node into the page file\n" );
              return rc;
            }

            return 0;
        }
    }

    else // non Leaf , insert key and rid to childPtr
    {
        BTNonLeafNode node;
        node.read(currPid,pf);
        PageId childPid;
        int keyPassed;

        node.locateChildPtr(key,childPid);
        if ( ( rc = insertRecursive( key, rid, childPid, height-1, overflow, keyPassed ) ) < 0 )
        {
            fprintf( stderr, "Error: while inserting to the child node with pid %d\n", childPid );
            return rc;
        }

        if( overflow ) //if child overflow
        {
            if (node.isFull())//node full, insert the keypassed back with lastPid, and split, change keyBack and return overflow.
            {
                BTNonLeafNode newNode;
                if ( ( rc = node.insertAndSplit( keyPassed, pf.endPid()-1, newNode, keyBack ) ) < 0 )
                {
                    fprintf( stderr, "Error: while insertAndSplit to the node with pid %d\n", currPid );
                    return rc;
                }

                if( ( rc = node.write(currPid,pf) ) < 0 )
                    return rc;

                if( ( rc = newNode.write(pf.endPid(),pf) ) < 0 )
                    return rc;

                overflow = true;
                return 0;
            }

            else //node not full, just insert the keypassed back with lastPid, set overflow to false
            {
                if( ( rc = node.insert(keyPassed,pf.endPid()-1) ) < 0 )
                    return rc;
                if( ( rc = node.write(currPid,pf) ) < 0 )
                    return rc;

                overflow = false;
                return 0;
            }
        }

    }

    return 0;
}


/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
    RC rc;

    if( ( rc = find(searchKey,cursor,rootPid,treeHeight) ) < 0 )
        return rc;

    return 0;
}


/*
 * Recursively locate the searchKey, and output the location of the entry in cursor.
 * The currPid is the page id of the root of the subtree at the current level.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry with the key value.
 * @param currPid[IN] the page id of the root of the subtree at the current level.
 * @param height[IN] the height of the subtree.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::find(const int key, IndexCursor& cursor, PageId currPid, int height)
{
    RC rc;

    // if the height is 1, which means at the leaf node.
    if(height == 1)
    {
        int eid;
        BTLeafNode l;
        if( ( rc = l.read(currPid,pf) ) < 0 )
            return rc;

        if( ( rc = l.locate(key,eid) ) < 0 )
            return rc;

        cursor.eid = eid;
        cursor.pid = currPid;
    }

    // if the height is not 0, which means at the non-leaf node.
    else
    {
        PageId pid;
        BTNonLeafNode n;
        if( ( rc = n.read(currPid,pf) ) < 0 )
            return rc;

        if( ( rc = n.locateChildPtr(key,pid) ) < 0 )
            return rc;

        if( ( rc = find(key, cursor, pid, height-1) ) < 0 )
            return rc;
    }

    return 0;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * If the cursor.eid is the last entry id of the current node,
 * and the page at cursor.pid does not have next sibling, return RC_END_OF_TREE.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
    BTLeafNode leaf;
    leaf.read(cursor.pid,pf);

    if(cursor.eid < 0 || cursor.eid > leaf.getKeyCount()-1)
        return RC_INVALID_CURSOR;

    leaf.readEntry(cursor.eid,key,rid);
    if(cursor.eid==leaf.getKeyCount()-1) //if eid points to last eid, set pid to next leaf, and eid = 0
    {
        /*
         * If the next node pointer is -1, then it doesn't have the next node,
         * and return the error RC_END_OF_TREE, indicating it's the end of tree,
         * and can't readForward any more.
         */
        if(leaf.getNextNodePtr() == -1)
            return RC_END_OF_TREE;

        // if the current node has the next sibling
        cursor.pid = leaf.getNextNodePtr();
        cursor.eid = 0;
    }
    else cursor.eid++;

    return 0;
}

IndexCursor BTreeIndex::getLeastKeyCursor()
{
        return findLeastKeyCursor( rootPid, treeHeight );
}

IndexCursor BTreeIndex::findLeastKeyCursor(PageId currPid, int h)
{
	if(h==1)
	{
		IndexCursor ic;
		ic.eid = 0; 
		ic.pid = currPid;
		return ic;
	}
	BTNonLeafNode node;
	node.read(currPid,pf);
        return findLeastKeyCursor(node.getPid(0),h-1);
}
